A low-density parity-check (LDPC) code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over a Galois Field GF(q), q≧2. If q=2, the code is a binary code. All linear block codes can be described as the product of a k-bit information vector s1×k with a code generator matrix Gk×n to produce an n-bit codeword x1×n, where the code rate is r=k/n. The codeword x is transmitted through a noisy channel, and the received signal vector y is passed to the decoder to estimate the information vector s1×k.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix Hm×n span the m-dimensional dual space C⊥, where m=n−k. Since x=sG and GHT=0, it follows that xHT=0 for all codewords in subspace C, where “T” (or “T”) denotes matrix transpose. In the discussion of LDPC codes, this is generally written asHXT=0T,  (1)where 0 is a row vector of all zeros, and the codeword x=[s p]=[s0, s1, . . . , sk−1, p0, p1, . . . , pm−1], where p0, . . . , pm−1 are the parity-check bits and s0, . . . , sk−1 are the systematic bits, equal to the information bits within the information block.
For an LDPC code the density of non-zero entries in H is low, i.e., there are only a small percentage of 1's in H, allowing better error-correcting performance and simpler decoding than using a dense H. A parity-check matrix can be also described by a bipartite graph. The bipartite graph is not only a graphic description of the code but also a model for the decoder. In the bipartite graph, a codeword bit (therefore each column of H) is represented by a variable node on the left, and each parity-check equation (therefore each row of H) is represented by a check node on the right. Each variable node corresponds to a column of H and each check node corresponds to a row of H, with “variable node” and “column” of H referred to interchangeably, as are “check node” and “row” of H. The variable nodes are only connected to check nodes, and the check nodes are only connected to variable nodes. For a code with n codeword bits and m parity bits, variable node vj is connected to check node ci by an edge if codeword bit j participates in check equation i, i=0, 1, . . . , m−1, j=0, 1, . . . , n−1. In other words, variable node j is connected to check node i if entry hij of the parity-check matrix H is 1. Mirroring Equation (1), the variable nodes represent a valid codeword if all check nodes have even parity.
An example is shown below to illustrate the relationship between the parity-check matrix, the parity-check equations, and the bipartite graph. Let an n=12, rate-½ code be defined by
                              H          =                                                                      [                                                                                    1                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                                                            1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                                                            0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                                                            0                                                                    0                                                                    0                                                                    1                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                              ]                                }                                            ︸                n                                      ⁢            m                          ,                            (        2        )            with the left side portion corresponding to k (=6) information bits s, the right side portion corresponding to m (=6) parity bits p. Applying (1), the H in (2) defines 6 parity-check equations as follows:
                    {                                                                                                  x                    0                                    +                                      x                    2                                    +                                      x                    6                                    +                                      x                    7                                                  =                0                                                                                                                              x                    1                                    +                                      x                    4                                    +                                      x                    7                                    +                                      x                    8                                                  =                0                                                                                                                              x                    2                                    +                                      x                    5                                    +                                      x                    6                                    +                                      x                    8                                    +                                      x                    9                                                  =                0                                                                                                                              x                    0                                    +                                      x                    3                                    +                                      x                    9                                    +                                      x                    10                                                  =                0                                                                                                                              x                    1                                    +                                      x                    4                                    +                                      x                    10                                    +                                      x                    11                                                  =                0                                                                                                                              x                    3                                    +                                      x                    5                                    +                                      x                    6                                    +                                      x                    11                                                  =                0                                                                        (        3        )            H also has the corresponding bipartite graph shown in FIG. 1.
A bipartite graph of a good finite length LDPC code inevitably has cycles. A cycle of length 2d (denoted as cycle-2d) is a path of 2d edges which passes through d variable nodes and d check nodes and connects each node to itself without repeating any edge. Short cycles, especially cycle-4, degrade the performance of an iterative decoder and are normally avoided in the code design.
When the code size becomes large, it is difficult to encode and decode a randomly constructed LDPC code. Instead of directly building a large m×n pseudo-random H matrix, a structured LDPC design starts with a small mb×nb base matrix Hb, makes z copies of Hb, and interconnects the z copies to form a large m×n H matrix, where m=mb×z, n=nb×z. Using the matrix representation, to build H from Hb each 1 in Hb is replaced by a z×z permutation submatrix, and each 0 in Hb is replaced by a z×z all-zero submatrix. It has been shown that the permutation can be very simple without compromising performance. For instance, a simple circular right shift, where the permutation submatrix is obtained by circularly right shifting the columns of an identity matrix by a given amount, can be used without degrading decoding performance. Since circular left shift (x mod z) times is equivalent to circular right shift ((z−x) mod z) times, this text only discusses circular right shift and refers to it as a circular shift for brevity. With this constraint, each H matrix can be uniquely represented by an mb×nb model matrix Hbm, which is obtained by replacing each hij=0 in Hb by p(i, j)=−1 to denote a z×z all-zero matrix, and replacing each hij=1 in Hb by a circular shift size p(i, j)≧0.
Thus instead of using the expanded matrix H, a code is uniquely defined by the model matrix Hbm. Both encoding and decoding can be performed based on a much smaller mb×nb Hbm and vectors of bits, with each vector having size z.
This procedure essentially maps each edge of Hb to a vector edge of size z in H (represented by p(i, j) of Hbm), each variable node of Hb to a vector variable node of length z in H (corresponding to a column of Hbm), and each check node of Hb to a vector check node of length z in H (corresponding to a row of Hbm). In a structured design, the randomness is built in H through two stages: (a) the pseudo-random base matrix Hb; (b) the pseudo-random shift of the edges within each vector edge. Storage and processing complexity of a structured design are low because both stages of randomization are very simple.
Frequently a system such as that defined in the IEEE 802.16 standard is required to provide error-correcting codes for a family of codes of size (nf, kf), where all the codes within the family have the same code rate R=kf/nf and the code size scaled from a base size, nf=zf×nb, kf=zf×kb, f=0, 1, . . . , fmax, where (fmax+1) is the total number of members in the code family, and zf is the expansion factor for the f-th code in the family. For these systems, it is possible to derive codes for all (nf, kf) from one base matrix Hb and a set of appropriate zf. Let p(f, i, j) be the shift size of the vector edge located at position (i, j) within the f-th model matrix Hbm(f) of expansion factor zf. Thus the set of shift sizes {p(f, i, j)} and the model matrix Hbm(f) can be referred to interchangeably.
However, it is not clear how to define shift sizes p(f, i, j) for each Hbm(f). One way to define a family of codes is to search for the base matrix Hb and/or p(f, i, j), 0≦i≦m−1, 0≦j≦n−1, independently for all given f However, this approach requires that Hb and/or p(f, i, j), 0≦i≦m−1, 0≦j≦n−1, be specified and stored for all f.
Since Hb defines the basic structure and message interconnection of the LDPC decoder, it would be preferred to reuse Hb for all codes in a family. When the same Hb is shared by all codes in a family,                Shift size p(f, i, j)=−1 when entry (i, j) of Hb is 0. Shift size p(f, i, j)=−1 is used to denote a zf×zf all-zero submatrix that is used to replace entry (i, j) of model matrix Hbm(f) in expanding to the binary parity-check matrix H(f). If entry (i, j) of Hb is 0, p(f, i, j) is the same for any f, i.e., p(f, i, j)≡−1. Note that “−1” is only a label for the all-zero submatrix, and any other label that is not a non-negative integer can be used equivalently, e.g., “−2” or “∞”.        Shift size p(f, i, j)≧0 when entry (i, j) of Hb is 1. Shift size p(f, i, j)≧0 is used to denote a zf×zf identity submatrix circular right shifted by p(f, i, j) columns. The submatrix is used to replace entry (i, j) of model matrix Hbm(f) in expanding to the binary parity-check matrix H(f). The value of p(f, i, j) may be different for different f, i.e., entry (i, j) of Hbm(f) may be different for different f.        
As to the value of non-negative p(f, i, j), it has been proposed to use p(f, i, j)=p(i, j) mod zf for any zf, where the set of shift sizes {p(i, j)} is the same for all zf. Thus only one set of {p(i, j)} needs to be specified, and it potentially reduces the complexity of implementing codes of different zf. However, due to the effect of the modulo operation, a set of {p(i, j)} designed to avoid bad cycle patterns for one zf may cause a large number of cycles and low weight codewords for another zf, resulting in degraded error-correcting performance for some (nf, kf).
Therefore, there is a need for a method to derive shift sizes {p(f, i, j)} from one set of {p(i, j)} while maintaining the desired code properties for all code sizes (nf, kf).